package pers.qianyu.month_202011.date_20201128;

/**
 * 494. 目标和
 * https://leetcode-cn.com/problems/target-sum/
 *
 * @author mizzle rain
 * @date 2020-11-28 15:07
 */
public class FindTargetSumWays2 {
    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return recur(nums, 0, S);
    }

    private int recur(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return rest != 0 ? 0 : 1;
        }
        int res = 0;
        for (int i : new int[]{1, -1}) {
            rest -= i * nums[index];
            res += recur(nums, index + 1, rest);
            rest += i * nums[index];
        }
        return res;
    }
}
